@incollection{Lengauer90,
  author    = {Thomas Lengauer},
  title     = {{\sc VLSI} Theory},
  booktitle = {Handbook of Theoretical Computer Science, Volume A: Algorithms
               and Complexity (A)},
  year      = {1990},
  pages     = {835-868},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{ChuS91,
  author    = {Jeff I. Chu and
               Georg Schnitger},
  title     = {The communication complexity of several problems in matrix
               computation},
  journal   = {J. Complexity},
  volume    = {7},
  number    = {4},
  year      = {1991},
  pages     = {395-407},
  ee        = {http://dx.doi.org/10.1016/0885-064X(91)90027-U},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{PapadopoulosYP07,
  author    = {Stavros Papadopoulos and
               Yin Yang and
               Dimitris Papadias},
  title     = {CADS: Continuous Authentication on Data Streams},
  booktitle = {VLDB},
  year      = {2007},
  pages     = {135-146},
  ee        = {http://www.vldb.org/conf/2007/papers/research/p135-papadopoulos.pdf},
  crossref  = {DBLP:conf/vldb/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{YiLHKS08,
  author    = {Ke Yi and
               Feifei Li and
               Marios Hadjieleftheriou and
               George Kollios and
               Divesh Srivastava},
  title     = {Randomized Synopses for Query Assurance on Data Streams},
  booktitle = {ICDE},
  year      = {2008},
  pages     = {416-425},
  ee        = {http://dx.doi.org/10.1109/ICDE.2008.4497450},
  crossref  = {DBLP:conf/icde/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{LiYHK07,
  author    = {Feifei Li and
               Ke Yi and
               Marios Hadjieleftheriou and
               George Kollios},
  title     = {Proof-Infused Streams: Enabling Authentication of Sliding
               Window Queries On Streams},
  booktitle = {VLDB},
  year      = {2007},
  pages     = {147-158},
  ee        = {http://www.vldb.org/conf/2007/papers/research/p147-li.pdf},
  crossref  = {DBLP:conf/vldb/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ChakrabartiCM09,
  author    = {Amit Chakrabarti and
               Graham Cormode and
               Andrew McGregor},
  title     = {Annotations in Data Streams},
  booktitle = {ICALP (1)},
  year      = {2009},
  pages     = {222-234},
  ee        = {http://dx.doi.org/10.1007/978-3-642-02927-1_20},
  crossref  = {DBLP:conf/icalp/2009-1},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{CormodeMT10,
  author    = {Graham Cormode and
               Michael Mitzenmacher and
               Justin Thaler},
  title     = {Streaming Graph Computations with a Helpful Advisor},
  journal   = {CoRR},
  volume    = {abs/1004.2899},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1004.2899},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{sipser96,
 author = {Sipser, Michael},
 title = {Introduction to the Theory of Computation},
 year = {1996},
 isbn = {053494728X},
 publisher = {International Thomson Publishing},
 }

@article{knuth2009art,
  title={{The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks \& Techniques; Binary Decision Diagrams}},
  author={Knuth, D.E.},
  year={2009},
  publisher={Addison-Wesley Professional}
}

@inproceedings{GoldwasserKR08,
  author    = {Shafi Goldwasser and
               Yael Tauman Kalai and
               Guy N. Rothblum},
  title     = {Delegating computation: interactive proofs for muggles},
  booktitle = {STOC},
  year      = {2008},
  pages     = {113-122},
  %crossref  = {DBLP:conf/stoc/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%@proceedings{DBLP:conf/stoc/2008,
%  editor    = {Richard E. Ladner and
%               Cynthia Dwork},
%  title     = {Proceedings of the 40th Annual ACM Symposium on Theory of
%               Computing, Victoria, British Columbia, Canada, May 17-20,
%               2008},
%  booktitle = {STOC},
%  publisher = {ACM},
%  year      = {2008},
%  isbn      = {978-1-60558-047-0},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@book{AignerZ03,
    abstract = {{From the Reviews:  "... Inside PFTB (Proofs from The Book) is indeed a glimpse of mathematical heaven, where clever insights and beautiful ideas combine in astonishing and glorious ways. There is vast wealth within its pages, one gem after another. Some of the proofs are classics, but many are new and brilliant proofs of classical results. ...Aigner and Ziegler... write: "... all we offer is the examples that we have selected, hoping that our readers will share our enthusiasm about brilliant ideas, clever insights and wonderful observations." I do. ... " Notices of the AMS, August 1999  "... the style is clear and entertaining, the level is close to elementary ... and the proofs are brilliant. ..." LMS Newsletter, January 1999 This third edition offers two new chapters,\&nbsp;on partition identities, and on card shuffling. Three proofs of Euler's most famous infinite series appear in a separate chapter. There is also a number of other improvements, such as an exciting new way to "enumerate the rationals".}},
    author = {Aigner, Martin and Ziegler, G\"{u}nter M.},
    citeulike-article-id = {465504},
    citeulike-linkout-0 = {http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&amp;path=ASIN/3540404600},
    citeulike-linkout-1 = {http://www.amazon.de/exec/obidos/redirect?tag=citeulike01-21&amp;path=ASIN/3540404600},
    citeulike-linkout-2 = {http://www.amazon.fr/exec/obidos/redirect?tag=citeulike06-21&amp;path=ASIN/3540404600},
    citeulike-linkout-3 = {http://www.amazon.jp/exec/obidos/ASIN/3540404600},
    citeulike-linkout-4 = {http://www.amazon.co.uk/exec/obidos/ASIN/3540404600/citeulike00-21},
    citeulike-linkout-5 = {http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/3540404600},
    citeulike-linkout-6 = {http://www.worldcat.org/isbn/3540404600},
    citeulike-linkout-7 = {http://books.google.com/books?vid=ISBN3540404600},
    citeulike-linkout-8 = {http://www.amazon.com/gp/search?keywords=3540404600&index=books&linkCode=qs},
    citeulike-linkout-9 = {http://www.librarything.com/isbn/3540404600},
    edition = {3rd},
    howpublished = {Hardcover},
    isbn = {3540404600},
    month = {November},
    posted-at = {2009-09-20 18:04:11},
    priority = {2},
    publisher = {Springer},
    title = {Proofs from THE BOOK},
    year = {2003}
}

@article{AroraS98,
  author    = {Sanjeev Arora and
               Shmuel Safra},
  title     = {Probabilistic Checking of Proofs: A New Characterization
               of {\sc NP}},
  journal   = {J. ACM},
  volume    = {45},
  number    = {1},
  year      = {1998},
  pages     = {70-122},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also appeared in FOCS'92}
}


@article{AroraLMSS98,
  author    = {Sanjeev Arora and
               Carsten Lund and
               Rajeev Motwani and
               Madhu Sudan and
               Mario Szegedy},
  title     = {Proof Verification and the Hardness of Approximation Problems},
  journal   = {J. ACM},
  volume    = {45},
  number    = {3},
  year      = {1998},
  pages     = {501-555},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Dinur07,
  author    = {Irit Dinur},
  title     = {The {\sc PCP} theorem by gap amplification},
  journal   = {J. ACM},
  volume    = {54},
  number    = {3},
  year      = {2007},
  pages     = {12},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also appeared in STOC'06}
}

@article{Goldreich02,
 author = {Goldreich,, Oded},
 title = {Property testing in massive graphs},
 book = {Handbook of massive data sets},
 year = {2002},
 isbn = {1-4020-0489-3},
 pages = {123--147},
 publisher = {Kluwer Academic Publishers},
 address = {Norwell, MA, USA},
 }


@inproceedings{Yao79,
  author    = {Andrew Chi-Chih Yao},
  title     = {Some Complexity Questions Related to Distributive Computing
               (Preliminary Report)},
  booktitle = {STOC},
  year      = {1979},
  pages     = {209-213},
  crossref  = {DBLP:conf/stoc/STOC11},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%@proceedings{DBLP:conf/stoc/STOC11,
%  title     = {Conference Record of the Eleventh Annual ACM Symposium on
%               Theory of Computing, 30 April-2 May, 1979, Atlanta, Georgia,
%               USA},
%  booktitle = {STOC},
%  publisher = {ACM},
%  year      = {1979},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@article{LamR92,
  author    = {Tak Wah Lam and
               Walter L. Ruzzo},
  title     = {Results on Communication Complexity Classes},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {44},
  number    = {2},
  year      = {1992},
  pages     = {324-342},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also appeared in Structure in Complexity Theory Conference 1989}
}


@inproceedings{ChakrabartiCM08,
  author    = {Amit Chakrabarti and
               Graham Cormode and
               Andrew McGregor},
  title     = {Robust lower bounds for communication and stream computation},
  booktitle = {STOC},
  year      = {2008},
  pages     = {641-650},
  ee        = {http://doi.acm.org/10.1145/1374376.1374470},
  %crossref  = {DBLP:conf/stoc/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%@proceedings{DBLP:conf/stoc/2008,
%  editor    = {Richard E. Ladner and
%               Cynthia Dwork},
%  title     = {Proceedings of the 40th Annual ACM Symposium on Theory of
%               Computing, Victoria, British Columbia, Canada, May 17-20,
%               2008},
%  booktitle = {STOC},
%  publisher = {ACM},
%  year      = {2008},
%  isbn      = {978-1-60558-047-0},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@misc{Amazon,
    address = {http://aws.amazon.com/ec2/},
    citeulike-article-id = {3486797},
    keywords = {cited\_in\_masters},
    posted-at = {2008-11-07 07:42:46},
    priority = {2},
    title = {Amazon Elastic Compute Cloud (Amazon EC2)}
}


@article{PapadimitriouS84,
  author    = {Christos H. Papadimitriou and
               Michael Sipser},
  title     = {Communication Complexity},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {28},
  number    = {2},
  year      = {1984},
  pages     = {260-269},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also appeared in STOC'82}
}


@article{FKMSZ-TCS05,
 author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor and Siddharth Suri and Jian Zhang},
 title = {On graph problems in a semi-streaming model},
 journal = {Theor. Comput. Sci.},
 volume = {348},
 number = {2},
 year = {2005},
 issn = {0304-3975},
 pages = {207--216},
 publisher = {Elsevier Science Publishers Ltd.},
 address = {Essex, UK},
 }

 @inproceedings{FKMSS-SODA05,
 author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor and Siddharth Suri and Jian Zhang},
 title = {Graph distances in the streaming model: the value of space},
 booktitle = {SODA},
 year = {2005},
 isbn = {0-89871-585-7},
 pages = {745--754}
 }


@inproceedings{HajnalMT88,
  author    = {Andr{\'a}s Hajnal and
               Wolfgang Maass and
               Gy{\"o}rgy Tur{\'a}n},
  title     = {On the Communication Complexity of Graph Properties},
  booktitle = {STOC},
  year      = {1988},
  pages     = {186-191},
  crossref  = {DBLP:conf/stoc/STOC20},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%@proceedings{DBLP:conf/stoc/STOC20,
%  title     = {Proceedings of the Twentieth Annual ACM Symposium on Theory
%               of Computing, 2-4 May 1988, Chicago, Illinois, USA},
%  booktitle = {STOC},
%  publisher = {ACM},
%  year      = {1988},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@inproceedings{DFR06,
 author = {Camil Demetrescu and Irene Finocchi and Andrea Ribichini},
 title = {Trading off space for passes in graph streaming problems},
 booktitle = {SODA},
 year = {2006},
 isbn = {0-89871-605-5},
 pages = {714--723}
 }





@article{AMS99,
 author = {Noga Alon and Yossi Matias and Mario Szegedy},
 title = {The space complexity of approximating the frequency moments},
 journal = {J. Comput. Syst. Sci.},
 volume = {58},
 number = {1},
 year = {1999},
 issn = {0022-0000},
 pages = {137--147},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 note   = {Also appeared in STOC'96}
 }

@article{HRR99,
 author = {Monika R. Henzinger and Prabhakar Raghavan and Sridhar Rajagopalan},
 title = {Computing on data streams},
 book = {External memory algorithms},
 year = {1999},
 isbn = {0-8218-1184-3},
 pages = {107--118},
 publisher = {American Mathematical Society},
 address = {Boston, MA, USA},
 }

@article{MP78,
  author    = {J. Ian Munro and
               Mike Paterson},
  title     = {Selection and Sorting with Limited Storage},
  journal   = {Theor. Comput. Sci.},
  volume    = {12},
  year      = {1980},
  pages     = {315-323},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also appeared in FOCS'78}
}


@inproceedings{patrascu08median,
  author    = {Amit Chakrabarti and
               T. S. Jayram and
               Mihai Patrascu},
  title     = {Tight lower bounds for selection in randomly ordered streams},
  booktitle = {SODA},
  year      = {2008},
  pages     = {720-729},
  ee        = {http://doi.acm.org/10.1145/1347082.1347161},
  crossref  = {DBLP:conf/soda/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
%@proceedings{DBLP:conf/soda/2008,
%  editor    = {Shang-Hua Teng},
%  title     = {Proceedings of the Nineteenth Annual ACM-SIAM Symposium
%               on Discrete Algorithms, SODA 2008, San Francisco, California,
%               USA, January 20-22, 2008},
%  booktitle = {SODA},
%  publisher = {SIAM},
%  year      = {2008},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}


@inproceedings{GM06,
 author = {Sudipto Guha and Andrew McGregor},
 title = {Approximate quantiles and the order of the stream},
 booktitle = {PODS},
 year = {2006},
 isbn = {1-59593-318-2},
 pages = {273--279}
 }

%@proceedings{DBLP:conf/pods/2006,
%  editor    = {Stijn Vansummeren},
%  title     = {Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART
%               Symposium on Principles of Database Systems, June 26-28,
%               2006, Chicago, Illinois, USA},
%  booktitle = {PODS},
%  publisher = {ACM},
%  year      = {2006},
%  isbn      = {1-59593-318-2},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@INPROCEEDINGS{GM07,


    author = {Sudipto Guha and Andrew Mcgregor},
    title = {Lower bounds for quantile estimation in random-order and multi-pass streaming},


    booktitle = {ICALP},


    year = {2007},
    pages = {704--715}


}

@article{ADRR04,
author = {Gagan Aggarwal and Mayur Datar and Sridhar Rajagopalan and Matthias Ruhl},
title = {On the Streaming Model Augmented with a Sorting Primitive},
journal ={FOCS},
year = {2004},
issn = {0272-5428},
pages = {540-549}
}




@inproceedings{FKSV00,
 author = {J. Feigenbaum and S. Kannan and M. Strauss and M. Viswanathan},
 title = {Testing and spot-checking of data streams},
 booktitle = {SODA},
 year = {2000},
 pages = {165--174}
 }

@phdthesis{R03,
 author = {Jan Matthias Ruhl},
 note = {Supervisor-David R. Karger},
 title = {Efficient algorithms for new computational models},
 year = {2003},
 order_no = {AAI0805714},
 publisher = {Massachusetts Institute of Technology},
 }

@inproceedings{EKR99,
 author = {Funda Erg\"{u}n and Ravi Kumar and Ronitt Rubinfeld},
 title = {Fast approximate PCPs},
 booktitle = {STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of computing},
 year = {1999},
 isbn = {1-58113-067-8},
 pages = {41--50},
 location = {Atlanta, Georgia, United States},
 doi = {http://doi.acm.org/10.1145/301250.301267},
 publisher = {ACM},
 address = {New York, NY, USA},
 }

@book{KNbook,
 author = {Eyal Kushilevitz and Noam Nisan},
 title = {Communication complexity},
 year = {1997},
 isbn = {0-521-56067-5},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@article{HW07,
 author = {Johan H{\aa}stad and Avi Wigderson},
 title = {The Randomized Communication Complexity of Set Disjointness},
 journal = {Theory of Computing},
 year = {2007},
 volume = {3},
 number = {1},
 pages = {211-219},
 publisher = {Theory of Computing}
}

@inproceedings{patrascu08structures,
  author =    "Mihai P{\v a}tra{\c s}cu",
  title =     "(Data) STRUCTURES",
  booktitle = "Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS)",
  year =      "2008",
  note =      "To appear"
}

@inproceedings{Lipton90,
  author    = {Richard J. Lipton},
  title     = {Efficient Checking of Computations},
  booktitle = {STACS},
  year      = {1990},
  pages     = {207-215},
  crossref  = {DBLP:conf/stacs/1990},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%@proceedings{DBLP:conf/stacs/1990,
%  editor    = {Christian Choffrut and
%               Thomas Lengauer},
%  title     = {STACS 90, 7th Annual Symposium on Theoretical Aspects of
%               Computer Science, Rouen, France, February 22-24, 1990, Proceedings},
%  booktitle = {STACS},
%  publisher = {Springer},
%  series    = {Lecture Notes in Computer Science},
%  volume    = {415},
%  year      = {1990},
%  isbn      = {3-540-52282-4},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}

@TECHREPORT{Lipton89,
  AUTHOR =       {Richard J. Lipton},
  TITLE =        {Fingerprinting Sets},
  INSTITUTION =  {Princton University},
  YEAR =         {1989},
  type =         {CS-TR-212-89},
}


 @inproceedings{GopalanR09,
  author    = {Parikshit Gopalan and
               Jaikumar Radhakrishnan},
  title     = {Finding duplicates in a data stream},
  booktitle = {SODA},
  year      = {2009},
  pages     = {402-411},
  ee        = {http://doi.acm.org/10.1145/1496770.1496815},
  crossref  = {DBLP:conf/soda/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
%@proceedings{DBLP:conf/soda/2009,
%  editor    = {Claire Mathieu},
%  title     = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on
%               Discrete Algorithms, SODA 2009, New York, NY, USA, January
%               4-6, 2009},
%  booktitle = {SODA},
%  publisher = {SIAM},
%  year      = {2009},
%  bibsource = {DBLP, http://dblp.uni-trier.de}
%}
